
//20211002
/**
 * 
 * 最大子序和:
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 


解题方式：
1.动态规划-O(n)
2.分治法-比较复杂，待学习，可以到达O(log(n))
*/

/**
 * 解题思路：
 * 暴力破解，把所有的组合的和解出来后，再获取最大值
 * 时间复杂度：O(N平方))
 * 空间复杂度：O(N+M)
 * @param {number[]} nums
 * @return {number}
 */
 var maxSubArray = function(nums) {
    let max=nums[0];

        for (let i = 0; i < nums.length; i++) {
            //console.log(nums[i]);
           sum=0;
           console.log('------')
           //  let array=[];
            for (let j = i; j < nums.length; j++) {
               console.log(i,j,nums[j])
                 sum += nums[j];
                 max=Math.max(sum,max);    
            }
        }

     return max;
};

//const nums = [-2,1,-3,4,-1,2,1,-5,114];
// const nums = [1,-114];
// console.log(maxSubArray(nums));


/**
 * 最优解
 * 解题思路：
 * 动态规划：
 * 1个记录目前为止最大的和
 * 1个记录上一次最优的和
 * 公式
 * f(i)=max(max,max(sum+nums[i],nums[i]))
 * 时间复杂度：O(N)
 * 空间复杂度：O(2)
 * @param {number[]} nums
 * @return {number}
 */
 var maxSubArray2 = function(nums) {
    let max=nums[0];
    let sum=0;
        for (let i = 0; i < nums.length; i++) {
           sum=Math.max(sum+nums[i],nums[i]);//取累积和 和 当前数字的较大值，如果当前值比之前的和大，则舍弃之前的和
           max=Math.max(max,sum);//取当前和 和 之前的最大的和 的较大值
        }

     return max;
};

const nums2 = [-2,1,-3,4,-1,2,1,-5,114];
//const nums2 = [1,-114];
console.log(maxSubArray2(nums2));